package com.example.algorithm.huawei_rongyao_29;
import java.util.Scanner;

// 找到搜索二叉树中两个错误的节点   明天再看

/**
 标题：找到搜索二叉树中两个错误的节点 | 时间限制：2秒 | 内存限制：262144K
 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
 搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。
 输入
 {1,2,3}
 输出
 [1,2]

 要解决这个问题，我们需要找到原本是二叉搜索树（BST）中被错误交换的两个节点。我们可以利用BST的中序遍历特性（中序遍历结果是一个有序序列）来检测这两个错误的节点。

 思路
 中序遍历BST：中序遍历BST得到的结果应该是一个递增的有序序列。
 检测逆序对：在中序遍历结果中找到不满足递增顺序的两个节点。
 输出结果：这两个节点即为被交换的节点。
 具体步骤如下：

 进行中序遍历并记录节点的值。
 找到中序遍历结果中第一个和第二个逆序对。
 第一个逆序对的第一个节点和第二个逆序对的第二个节点即为错误交换的两个节点。

 如下图：如果节点 2 与节点 5 调换了位置，得到的数组中有两个逆序对。

 第一个错误节点：第一次下降的前一个节点。
 第二个错误节点：最后一次下降的一个节点。
 * */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public class Q12_IncorrectBSTNodes {
    private TreeNode first = null;
    private TreeNode second = null;
    private TreeNode prev = new TreeNode(Integer.MIN_VALUE);

    public int[] findSwappedNodes(TreeNode root) {
        // 进行中序遍历并找出错误节点
        inorderTraversal(root);
        return new int[] {first.val, second.val};
    }

    private void inorderTraversal(TreeNode root) {
        if (root == null) return;

        inorderTraversal(root.left);

        // 发现第一个错误节点
        if (first == null && prev.val > root.val) {
            first = prev;
        }
        // 发现第二个错误节点
        if (first != null && prev.val > root.val) {
            second = root;
        }

        prev = root;

        inorderTraversal(root.right);
    }


}


